package com.zhn;

/**
 * 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 * 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
 *
 * 示例 1：
 * 输入：nums = [2,3,1,1,4]
 * 输出：true
 * 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标
 */
public class CanJump {
    public static void main(String[] args) {
        int[] arr = {2,3,1,1,4};
        boolean b = canJump(arr);
        System.out.println(b);
    }
    public static boolean canJump(int[] nums) {
        if(nums.length == 1){
            return true;
        }
        int[] dp = new int[nums.length];
        //dp[i]：从[0,i]的任意一点处出发，你最大可以跳跃到的位置.
        dp[0] = nums[0];
        //如果把条件设置为i<nums.length，意味着还会遍历已经到终点再往后跳的条件，
        //不是它不能到达最后一位的条件，因为他现在已经在最后一位上了，没有必要再去判断一下
        for(int i = 1; i < nums.length-1; i++){
            //如果能到达的距离已经比当前距离i小，就直接返回false
            if(dp[i-1] < i)return false;
            dp[i] = Math.max(dp[i-1],i+nums[i]);
        }
        //比如有5个数字，距离应该是4
        //dp数组存的距离，dp[0]存放的就是第一个数字到第二个数字的距离，dp[1]就是第二个到第三个的距离，所以最后取最终数值应该是取length-2
        return dp[dp.length-2] >= nums.length-1;
    }
}
